|
In graph theory, two graphs and are homeomorphic if there is a graph isomorphism from some subdivision of to some subdivision of . If the edges of a graph are thought of as lines drawn from one vertex to another (as they are usually depicted in illustrations), then two graphs are homeomorphic to each other in the graph-theoretic sense precisely if they are homeomorphic in the sense in which the term is used in topology. ==Subdivision and smoothing == In general, a subdivision of a graph ''G'' (sometimes known as an expansion) is a graph resulting from the subdivision of edges in ''G''. The subdivision of some edge ''e'' with endpoints yields a graph containing one new vertex ''w'', and with an edge set replacing ''e'' by two new edges, and . For example, the edge ''e'', with endpoints : can be subdivided into two edges, ''e''1 and ''e''2, connecting to a new vertex ''w'': The reverse operation, smoothing out or smoothing a vertex ''w'' with regards to the pair of edges (''e''1 ,''e''2 ) incident on ''w'', removes both edges containing ''w'' and replaces (''e''1 ,''e''2 ) with a new edge that connects the other endpoints of the pair. Here it is emphasized that only 2-valent vertices can be smoothed. For example, the simple connected graph with two edges, ''e''1 and ''e''2 : has a vertex (namely ''w'') that can be smoothed away, resulting in: Determining whether for graphs ''G'' and ''H'', ''H'' is homeomorphic to a subgraph of ''G'', is an NP-complete problem.〔The more commonly studied problem in the literature, under the name of the subgraph homeomorphism problem, is whether a subdivision of ''H'' is isomorphic to a subgraph of ''G''. The case when ''H'' is an ''n''-vertex cycle is equivalent to the Hamiltonian cycle problem, and is therefore NP-complete. However, this formulation is only equivalent to the question of whether ''H'' is homeomorphic to a subgraph of ''G'' when ''H'' has no degree-two vertices, because it does not allow smoothing in ''H''. The stated problem can be shown to be NP-complete by a small modification of the Hamiltonian cycle reduction: add one vertex to each of ''H'' and ''G'', adjacent to all the other vertices. Thus, the one-vertex augmentation of a graph ''G'' contains a subgraph homeomorphic to an (''n'' + 1)-vertex wheel graph, if and only if ''G'' is Hamiltonian. For the hardness of the subgraph homeomorphism problem, see e.g. .〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Homeomorphism (graph theory)」の詳細全文を読む スポンサード リンク
|